package com.lfg.leetcode.leetcode100;

import java.util.ArrayList;
import java.util.List;

public class No120minimumTotal {

    public static void main(String[] args) {
        List<List<Integer>> data = new ArrayList<>();
        int ret = minimumTotal(data);
        System.out.println("[" + ret + "]");
    }


    public static int minimumTotal(List<List<Integer>> triangle) {
        int[] ret = new int[triangle.get(triangle.size() - 1).size() + 1];
        for (int i = triangle.size() - 1; i >= 0; i--) {
            List<Integer> current = triangle.get(i);
            for (int j = 0; j < current.size(); j++) {
                ret[j] = Math.min(ret[j], ret[j + 1]) + current.get(j);
            }
        }
        return ret[0];
    }

    public static int minimumTotal2(List<List<Integer>> triangle) {
        int ret = Integer.MAX_VALUE;
        int triangleSize = triangle.size();
        for (int i = 1; i < triangleSize; i++) {
            List<Integer> lastRow = triangle.get(i - 1);
            List<Integer> current = triangle.get(i);
            for (int j = 0; j < current.size(); j++) {
                int data = current.get(j);
                int left = j - 1;

                int lastRowSize = lastRow.size();
                int total = Integer.MAX_VALUE;
                if (left >= 0 && left < lastRowSize) {
                    total = Math.min(data + lastRow.get(left), total);
                }
                if (j < lastRowSize) {
                    total = Math.min(data + lastRow.get(j), total);
                }
                current.set(j, total);
            }
        }
        List<Integer> row = triangle.get(triangleSize - 1);
        for (int i : row) {
            ret = Math.min(ret, i);
        }
        return ret;
    }
}
